package leetcode.leetcode_239;

import java.util.ArrayDeque;
import java.util.ArrayList;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i =0 ;i<k;i++){
            while(!deque.isEmpty()&&nums[deque.getLast()]<=nums[i]){
                deque.removeLast();
            }
            deque.addLast(i);
            int left = i -k+1;
            while (left>deque.getFirst()) deque.removeFirst();
            if (left>0){
                ans[left] = nums[deque.getFirst()];
            }
        }
        return ans;

    }

}